//avl树是最早的平衡二叉树
//平衡：左右子树的高度差不能超过1，否则这棵树就失衡了
//失衡点：左右子树高度超过1的节点


//四种失衡方式
//1.左左插入----右旋操作
//2.右右插入----左旋操作
//3.左右插入----左右旋操作
//4.右左插入----右左旋操作
#include <stdio.h>
#include <stdlib.h>

#define ElementType int

struct TreeNode
{
    ElementType data;
    struct TreeNode *left;
    struct TreeNode *right;
};
typedef struct TreeNode TNode;

//左旋
TNode* RotateLeft(TNode *root)
{
    TNode *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}

//右旋
TNode* RotateRight(TNode *root)
{
    TNode *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}

//左右旋
TNode* RotateLeftRight(TNode *root)
{
    root->left = RotateLeft(root->left);
    return RotateRight(root);
}

//右左旋
TNode* RotateRightLeft(TNode *root)
{
    root->right = RotateRight(root->right);
    return RotateLeft(root);
}

//判断节点的高度
int GetNodeHeight(TNode *node)
{
    if(node == NULL)
        return 0;
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

//创建节点
TNode *CreateTNode(ElementType element)
{
    TNode *newNode = (TNode*)malloc(sizeof(TNode));
    if(newNode == NULL)
    {
        printf("create node malloc error!\n");
        return NULL;
    }

    newNode->data = element;
    newNode->left = newNode->right = NULL;
    return newNode;
}

//插入:有可能会导致树失衡进而导致根节点会变,所以返回值类型为TNode*
TNode *InsertTreeNode(TNode *root,ElementType element)
{
    if(root == NULL)
    {
        root = CreateTNode(element);
    }
    else if(root->data > element)
    {
        //直接递归插入左子树
        root->left = InsertTreeNode(root->left,element);
        //root为失衡点
        if(GetNodeHeight(root->left) - GetNodeHeight(root->right) > 1)
        {
            //左左插入
            if(root->left->data > element)
                root = RotateRight(root);
            //左右插入
            else
                root = RotateLeftRight(root);
        }
    }
    else
    {
        //递归插入右子树
        root->right = InsertTreeNode(root->right,element);
        if(GetNodeHeight(root->right) - GetNodeHeight(root->left) > 1)
        {
            //右右插入
            if(root->right->data < element)
                root = RotateLeft(root);
            //右左插入
            else
                root = RotateRightLeft(root);
        }
    }
    return root;
}

//自平衡删除
TNode* DeleteNode(TNode *root,ElementType element)
{
    if(root == NULL)
        return NULL;

    if(element < root->data)
    {
        root->left = DeleteNode(root->left,element);
        //右子树重
        if(GetNodeHeight(root->right) - GetNodeHeight(root->left) > 1)
        {
            //右孩子的左子树比右子树高
            //右左
            if(GetNodeHeight(root->right->left) - GetNodeHeight(root->right->right) > 0)
                root = RotateRightLeft(root);
            else
                root = RotateLeft(root);
        }
    }
    else if(element > root->data)
    {
        root->right = DeleteNode(root->right,element);
        //左边重
        if(GetNodeHeight(root->left) - GetNodeHeight(root->right) > 1)
        {
            //左左
            if(GetNodeHeight(root->left->left) - GetNodeHeight(root->left->right) > 0)
                root = RotateRight(root);
            //左右
            else
                root = RotateLeftRight(root);
        }
    }
    //找到要删除的节点
    else
    {
        
    }
}

void TravelPrev(TNode *root)
{
    if(root == NULL)
        return;
    printf("%d ",root->data);
    TravelPrev(root->left);
    TravelPrev(root->right);
}

void TravelMid(TNode *root)
{
    if(root == NULL)
        return;
    TravelMid(root->left);
    printf("%d ",root->data);
    TravelMid(root->right);
}


int main()
{
    TNode *root = NULL;
    for(int i = 0; i < 10; i++)
    {
        root = InsertTreeNode(root,i+1);
    }
    printf("前序遍历\n");
    TravelPrev(root);
    printf("\n中序遍历\n");
    TravelMid(root);
    printf("\n");
    return 0;
}